#include <stdio.h>
#include <stdlib.h>

// 自定义动态数组结构体
typedef struct{
  int *data; // 指向动态数组的指针
  size_t size; // 当前数组中有效元素的个数
  size_t capacity; // 总容量
} DynamicArray;

/**
 * @brief 初始化动态数组
 * @param arr, 动态数组结构体指针
 * @param initCapacity, 初始大小
 * @return 无
 */
void init(DynamicArray *arr, size_t initCapacity){
  // 动态分配数组空间
  arr->data=(int *)malloc(initCapacity*sizeof(int));
  arr->size=0; // 初始化可用元素大小
  arr->capacity = initCapacity;
}

/**
 * @brief 释放动态数组的内存
 * @param arr 要释放的动态数组指针
 * @return 无
 */
void destroy(DynamicArray *arr){
  free(arr->data); // 释放对内存空间的内存
  arr->size=0;
  arr->capacity=0;
}

/**
 * @brief 获取动态数组的长度(元素个数)
 * @param 动态数组指针
 * @return 元素个数
 */
size_t getSize(DynamicArray *arr){
  return arr->size;
}

/**
 * @brief 调整动态数组大小
 * @param
 * @return 无
 */
void resize(DynamicArray *arr, size_t newCapacity){
  // 重新分配数组空间
  arr->data=(int *)realloc(arr->data,newCapacity*sizeof(int));
  arr->capacity = newCapacity;
}

/**
 * @brief 在指定位置插入新元素
 * @param arr 动态数组指针
 * @param index 要插入的位置
 * @param element 新元素的值
 * @return 无
 */
void insertAt(DynamicArray *arr,size_t index, int element){
  if(index<0||index>arr->size){
    printf("插入的位置无效 ");
    return;
  }
  // 先判断是否还有可用空间
  if(arr->size>=arr->capacity){ // 空间满了
    // 扩容2倍
    size_t newCapacity = arr->capacity*2;
    resize(arr,newCapacity);
  }
  // 执行新元素插入前，腾出位置
  for(size_t i=arr->size;i>index;i--){
    arr->data[i] = arr->data[i-1];    
  }
  // 最后，将新元素插入到指定位置
  arr->data[index] = element;
  arr->size++; // 更新有效元素的个数
}

/**
 * @brief 在头部插入新元素
 * @param arr 动态数组指针
 * @param element 新元素的值
 * @return 无
 */
void insertHead(DynamicArray *arr, int element){
  insertAt(arr,0,element);
}
/**
 * @brief 在尾部插入新元素
 * @param arr 动态数组指针
 * @param element 新元素的值
 * @return 无
 */
void insertTail(DynamicArray *arr, int element){
  insertAt(arr,arr->size,element);
}

/**
 * @brief 删除指定位置的元素
 * @param arr 动态数组指针
 * @param element 要删除元素的下标
 * @return 删除成功后元素的值,-1:删除失败
 */
int removeAt(DynamicArray *arr, size_t index){
  if(index<0||index>=arr->size){
    return-1;
  }
  int val = arr->data[index];
  // 从指定位置起，挪动元素
  for(int i=index;i<arr->size-1;i++){
    arr->data[i] = arr->data[i+1];
  }
  // 更新有效元素个数
  arr->size--;
  return val;
}

/**
 * @brief 删除头部元素
 * @param arr 动态数组指针
 * @param element 要删除元素的下标
 * @return 删除成功后元素的值,-1:删除失败
 */
int removeHead(DynamicArray *arr, size_t index){
  removeAt(arr,0);
}

/**
 * @brief 删除尾部元素
 * @param arr 动态数组指针
 * @return 删除成功后元素的值,-1:删除失败
 */
int removeTail(DynamicArray *arr){
  removeAt(arr,arr->size-1);
}


void /**
* @brief 打印数组元素
* @param arr 动态数组指针
* @return 无
*/
printArr(DynamicArray *arr){
  for(int i=0;i<arr->size;i++){
    printf("%d ",arr->data[i]);
  }
  printf("\n");
}

int main(void){
  DynamicArray arr;
  // 初始化动态数组
  init(&arr,2);
  // 插入元素
  insertAt(&arr,0,10);
  insertAt(&arr,0,20);
  insertTail(&arr,30); // 尾部插入
  insertHead(&arr,5); // 头部插入
  printf("size:%zu\n",getSize(&arr));
  printArr(&arr);
  // 删除指定位置的元素
  // printf("%d\n",removeAt(&arr,0));
  printf("%d\n",removeTail(&arr));
  printArr(&arr);
  return 0;
}
